/**
 * 项目名称: 顺序存储.cpp
 * 项目路径: study/DataStructure/数据结构/树/二叉树
 * 编辑时间: 2024年07月30日20时56分31秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>
#define MaxSize 100

using namespace std;

struct TreeNode{
    int value; // 元素数据
    bool isEmpty; // 结点是否为空
};

TreeNode tree[MaxSize];

/**
 * 初始化二叉树
 */
void init(){
    for(int i = 0;i<MaxSize ; i++)
        tree[i].isEmpty = true;
}

/**
 * 向二叉树中插入数据
 * @param value
 * @return
 */
bool add(int value){
    int n =1;
    while (n<MaxSize){
        if(tree[n].isEmpty){
            tree[n].value = value;
            tree[n].isEmpty = false;
            break;
        }
        n++;
    }
    return true;
}

/**
 * 清空二叉树
 * @return
 */
bool clear(){
    for(int i =0;i<MaxSize;i++){
        tree[i].isEmpty = true;
        tree[i].value = 0;
    }
}

/**
 * 判断二叉树是否为空
 * @return
 */
bool isEmpty(){
    return tree[1].isEmpty;
}

/**
 * 获得根节点的值
 * @param data
 * @return
 */
bool getRoot(int *data){
    if(isEmpty())return false;
    *data = tree[1].value;
    return true;
}

/**
 * 获得二叉树深度
 * @return
 */
int getDepth(){
    int allNode = 0;
    for(int i = 1;i<MaxSize;i++){
        if(!tree[i].isEmpty) {
            allNode = i;
            break;
        }
    }
    int depth = 1;
    while (allNode >= pow(2,depth))depth++;
    return depth;
}

/**
 * 获得二叉树中某个结点的父节点
 * @param x
 * @return
 */
TreeNode getParent(TreeNode x){
    if(isEmpty())return tree[0];
    for(int i =1;i<MaxSize;i++)
        if(tree[i].value == x.value)
            return tree[i/2];
}

/**
 * 获得二叉树中某个节点的左儿子
 * @param x
 * @return
 */
TreeNode getLeftChild(TreeNode x){
    if(isEmpty())return tree[0];
    for(int i = 1;i<MaxSize;i++)
        if(tree[i].value == x.value)
            return tree[i*2];
}

/**
 * 获得二叉树中某个节点的右儿子
 * @param x
 * @return
 */
TreeNode getRightChild(TreeNode x){
    if(isEmpty())return tree[0];
    for(int i = 1;i<MaxSize;i++)
        if(tree[i].value == x.value)
            return tree[i*2+1];
}

/**
 * 获取二叉树中某个结点的左兄弟
 * @param x
 * @return
 */
TreeNode getLeftBrother(TreeNode x){
    if(isEmpty())return tree[0];
    for(int i = 1;i<MaxSize;i++)
        if(tree[i].value == x.value && i%2==1)
            return tree[i-1];
}

/**
 * 获得二叉树中某个结点的右兄弟
 * @param x
 * @return
 */
TreeNode getRightBrother(TreeNode x){
    if(isEmpty())return tree[0];
    for(int i = 1;i<MaxSize;i++)
        if(tree[i].value == x.value && i%2==0)
            return tree[i+1];
}

/**
 * 获取指定层数指定位置数据
 * @param level
 * @param num
 * @return
 */
TreeNode getValue(int level,int num){
    if(isEmpty())return tree[0];
    return tree[(int )pow(2,level-1)+num-1];
}

/**
 * 替换某指定位置的结点数据（将二叉树第level层第num个数据元素替换为value)
 * @param level
 * @param num
 * @param data
 * @return
 */
bool replace(int level,int num,int data){
    int i = (int ) pow(2,level -1)+num -1;
    // 双亲结点为空,无法赋值
    if(i%2==0) {
        if (tree[i / 2].isEmpty)return false;
    }
    else {
            if(tree[(i-1)/2].isEmpty)return false;
    }
    tree[i].value = data;
    return true;
}

//---------------------------------二叉树遍历--------------------------------
/**
 * 均利用递归方式进行遍历
 * @return
 */

/**
 * 先序访问输出
 * @param now
 */
void preOrderVisit(int now){
    cout<<tree[now].value<<" ";
    if(!tree[now*2].isEmpty)preOrderVisit(now*2);// 访问左子树
    if(!tree[now*2+1].isEmpty)preOrderVisit(now*2+1);// 访问右子树
}

/**
 * 先序遍历
 * @return
 */
bool preOrderTraverse(){
    if(isEmpty())return false;
    preOrderVisit(1);// 调用前序遍历函数
    cout<<endl;
    return true;
}

/**
 * 中序访问输出
 * @param now
 */
void inOrderVisit(int now){
    if(!tree[now*2].isEmpty)inOrderVisit(now*2);// 访问左子树
    cout<<tree[now].value<<" ";
    if(!tree[now*2+1].isEmpty)inOrderVisit(now*2+1);// 访问右子树
}

/**
 * 中序遍历
 * @return
 */
bool inOrderTraverse(){
    if(isEmpty())return false;
    inOrderVisit(1);
    cout<<endl;
    return true;
}

/**
 * 后序访问输出
 * @param now
 */
void postOrderVisit(int now){
    if(!tree[now*2].isEmpty)postOrderVisit(now*2);
    if(!tree[now*2+1].isEmpty)postOrderVisit(now*2+1);
    cout<<tree[now].value<<" ";
}

/**
 * 后序遍历
 * @return
 */
bool postOrderTraverse(){
    if(isEmpty())return false;
    postOrderVisit(1);
    cout<<endl;
    return true;
}

/**
 * 层序遍历
 * @return
 */
bool levelOrderTraverse(){
    if(isEmpty())return false;
    int level = 1;
    for(int i = level;i<=getDepth();i++){
        printf("第%d层: ",i);
        for(int j = 1;j<= pow(2,i-1);j++){
            cout<<getValue(i,j).value<<" ";
        }
        cout<<endl;
    }
    return true;
}
int main() {
    init();
    add(1);
    add(12);
    add(6);
    add(34);
    inOrderTraverse();
    replace(2,1,100);
    inOrderTraverse();

    return 0;
}
